from itertools import combinations

# 计算项集的支持度
"""
item_set：需要计算支持度的项集。
transactions：交易记录的列表。
"""
def calculate_support(item_set, transactions):
    count = 0
    for transaction in transactions:
        if item_set.issubset(transaction):
            count += 1
    return count

# 生成所有单项集
def generate_item_sets(transactions):
    item_sets = set()
    for transaction in transactions:
        for item in transaction:
            item_sets.add(frozenset([item]))  # 使用frozenset不可变集合表示项集
    return item_sets

# 生成候选项集的组合
def generate_combinations(item_sets, length):
    return set(combinations(item_sets, length))

# 执行 BUC 算法
def buc_algorithm(transactions, min_support):
    # 1. 从单项集开始
    item_sets = generate_item_sets(transactions)
    frequent_item_sets = {}

    # 2. 计算单项集支持度并筛选出频繁项集
    for item_set in item_sets:
        support = calculate_support(item_set, transactions)
        if support >= min_support:
            frequent_item_sets[item_set] = support

    # 3. 生成更大的项集并计算支持度
    k = 2  # 从二项集开始
    while True:
        candidates = set()
        # 生成k项集的候选集
        for item_set1, item_set2 in combinations(frequent_item_sets.keys(), 2):
            # 合并两个项集，如果它们的大小是k-1并且只有一个不同的项
            candidate = item_set1 | item_set2
            if len(candidate) == k:
                candidates.add(candidate)

        # 如果没有候选集，结束
        if not candidates:
            break

        # 计算候选集的支持度
        new_frequent_item_sets = {}
        for candidate in candidates:
            support = calculate_support(candidate, transactions)
            if support >= min_support:
                new_frequent_item_sets[candidate] = support

        # 更新频繁项集
        frequent_item_sets.update(new_frequent_item_sets)
        k += 1  # 处理下一个大小的项集

    return frequent_item_sets


